#include <stdio.h>
#include <stdlib.h>
/*
    数据结构：动态数组（空间不足时自动扩容）
    查找算法：二分查找
    删除算法：原地删除或更改长度
    排序算法：希尔排序，快速排序
*/
typedef struct {
    int* data;
    int size;
    int cap;
}DynamicArray;
void heapify(DynamicArray* arr,int n, int i)
{
    int largest = i;
    int left = i* 2 + 1;
    int right = i* 2 + 2;

    if(left < n && arr->data[left] > arr->data[largest])
    {
        largest = left;
    }
    if(right < n && arr->data[right] > arr->data[largest])
    {
        largest = right;
    }

    if( largest != i)
    {
        int temp = arr->data[i];
        arr->data[i] = arr->data[largest];
        arr->data[largest] = temp;

        heapify(arr,n,largest);
    }
}
void heapSort(DynamicArray* arr,int n)
{
    printf("You are using heap sort function\n");
    for(int i = n/2 - 1; i >= 0; i--)
    {
        heapify(arr,n,i);
    }

    for(int i = n - 1 ; i > 0 ; i--)
    {
        int temp = arr->data[0];
        arr->data[0] = arr->data[i];
        arr->data[i] = temp;

        heapify(arr,i,0);
    }
}
void merge(DynamicArray* arr, int m,int l,int r)
{
    int i,j,k;
    int n1 = m - l + 1;
    int n2 = r - m;
    int temp1[n1];
    int temp2[n2];

    for(i = 0;i < n1;i++)
    {
        temp1[i] = arr->data[l + i];
    }

    for(j = 0; j < n2; j++)
    {
        temp2[j] = arr->data[m + 1+j];
    }
    i = 0;
    j = 0;
    k = l;
    while(i < n1 && j < n2)
    {
        if(temp1[i] < temp2[j])
        {
            arr->data[k] = temp1[i];
            i++;
            k++;
        }
        else if(temp1[i] > temp2[j]){
            arr->data[k] =  temp2[j];
            j++;
            k++;
        }
    }
    while( i < n1)
    {
        arr->data[k] = temp1[i];
        i++;
        k++;
    }
    while(j < n2)
    {
        arr->data[k] = temp2[j];
        j++;
        k++;
    }
}

void mergeSort(DynamicArray* arr, int l ,int r)
{
    if(l < r)
    {
        int m = l + (r - l)/2;

        mergeSort(arr,l,m);
        mergeSort(arr,m + 1, r);

        merge(arr,m,l,r);
    }
}
void init(DynamicArray* arr, int initialCap){
    arr->data = (int*)malloc(initialCap*sizeof(int));
    arr->size = 0;
    arr->cap = initialCap;
}
void insert(DynamicArray* arr, int element){
    if(arr->size == arr->cap){
        arr->cap *= 2;
        arr->data = (int*)realloc(arr->data,arr->cap*sizeof(int));

    }
    arr->data[arr->size++] = element;
}
void swap(int* a, int* b){
    int t = *a;
    *a = *b;
    *b = t;
}
int partion(DynamicArray* arr, int low, int high){
    int pivot = arr->data[high];
    int i = low - 1;
    for(int j = low; j <= high - 1;j++){
        if(arr->data[j] <= pivot){
            i++;
            swap(&arr->data[i],&arr->data[j]);
        }
    }
    swap(&arr->data[i + 1],&arr->data[high]);
    return (i + 1);
}
void biSort(DynamicArray* arr,int low, int high){
   if(low < high){
    int pivot = partion(arr,low,high);
    biSort(arr,low, pivot - 1);
    biSort(arr,pivot + 1,high);
   }
}
int removeElement(DynamicArray* arr, int index){
    if(index == arr->size - 1){
        arr->size--;
    }
    if(index >= 0 && index < arr->size){
        for(int i = index; i < arr->size - 1; i++){
            arr->data[i] = arr->data[i+1];
        }
        return 0;
    }
    else{
        printf("Index out of range");
        return -1;
     }
}
void freeArray(DynamicArray* arr){
    free(arr->data);
    arr->data = NULL;
    arr->size = 0;
    arr->cap = 0;   
}
void insertionSort(DynamicArray* arr,int n){
    printf("<<<YOU ARE USING ISERTSORT FUNCTION\n");
    // for(int i = 1; i < n; i++){
    //    int j = i - 1;
    //    int key = arr->data[i];
    //    while(j >= 0 && arr->data[j] > key)
    //    {
    //     arr->data[j + 1] = arr->data[j];
    //     j = j - 1;
    //    }
    //    arr->data[j + 1] = key;
    // }

    for(int i = n - 2; i >=0; i--)
    {
     int temp = arr->data[i];
     int j = i;
     while( j < n - 1 && arr->data[j + 1] > temp)
     {
        arr->data[j] = arr->data[j + 1];
        j++;
     }
     arr->data[j] = temp;
    }
}
int biSearch(DynamicArray* arr,int low,int high,int element){
    int mid = (low + high)/2;
    // int low = 0;
    // int high = arr->size - 1;
    if(arr->data[mid] == element){
        printf("Find the position:%d\n",mid);
        return 1;
    }
    if(low > high){
        printf("No such element!\n");
        return 0;
    }
    if(element < arr->data[mid]){
        high = mid - 1;
        return biSearch(arr,low,mid - 1,element);
    }
    if(element > arr->data[mid]){
        low = mid + 1;
        return biSearch(arr,mid + 1,high,element);
    }
    return -1;
}
void shellSort(DynamicArray* arr, int n){
    printf("<<<YOU ARE USING SHELLSORT FUNCTION\n");
    for( int gap = n/2 ; gap > 0; gap /= 2)
    {
        for(int i = gap; i < n ; i++)
        {
            int temp = arr->data[i];
            int j = i;
            while( j >= gap && arr->data[j - gap] > temp)
            {
                arr->data[j] = arr->data[j -gap];
                j -= gap;
            }
            arr->data[j] = temp;
        }
    }
}

int getArray(DynamicArray* arr,int index){
    if(index >= 0 && index < arr->size){
        printf("INDEX:%d\n",arr->data[index]);
        return arr->data[index];
    }
    else{
        printf("Index out of bounds\n");
        return -1;
    }
}
int getAllArray(DynamicArray* arr){
    if(sizeof(*arr) != 0){
        printf("All Element\n");
        for(int index = 0; index <= arr->size - 1; index++){
            printf("Element%d\n",arr->data[index]);
        }
        return 0;
    }
    return -1;
}
void printIt(int param){
    printf("Iterator:%d\n",param);

}
void iterateArray(DynamicArray *arr , void (*callback)(int)){
    for (int i = 0; i < arr->size; i++){
        callback(arr->data[i]);
    }
}
int main(){
    DynamicArray arr;
    init(&arr,2);
    insert(&arr,1000);
    insert(&arr,900);
    insert(&arr,30);
    insert(&arr,5999);
    insert(&arr,200);
    insert(&arr,10);
    // biSort(&arr,0,5);
    // insertionSort(&arr,6);
    // shellSort(&arr,6);
    // heapSort(&arr,6);
    mergeSort(&arr,0,5);
    // biSearch(&arr,0,4,1);
    // removeElement(&arr,5);
    // getAllArray(&arr);
    iterateArray(&arr,printIt);
    return 0;

}